﻿
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;

using alib;
using alib.Debugging;
using alib.Enumerable;
using alib.Dictionary;
using alib.Collections.ReadOnly;

namespace agree
{
	using FeatMarkEdge = KeyValuePair<FeatMark, Edge>;

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
#if DEBUG
	[DebuggerTypeProxy(typeof(arraytfs_debug_display))]
#endif
	public abstract unsafe partial class WriteableTfs : _atfs_base
	//, IDictionary<FeatMark, Edge>, ICollection<FeatMarkEdge>, IEnumerable<FeatMarkEdge>, ICollection, IEnumerable
	{
		public WriteableTfs(IRtParent parent, IIdentity prv, Restrictor r)
			: base(parent, prv, r, Flags.None)
		{
			this.next_mark = 1;
			this._initialize(277);
		}

		protected int next_mark;

		public override int EdgeCount
		{
			[DebuggerStepThrough]
			get
			{
				Debug.Assert(c_act == count - freeCount);
				return c_act;
			}
		}

		public override int SlotCount
		{
			[DebuggerStepThrough]
			get { return count; }
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public sealed override SlotRefArray SlotRefArray
		{
			get
			{
				int[] arr = new int[c_act + 1];
				for (int i = 0, j = 0; i <= c_act; j++)
					if (entries[j].hash_code != -1)
						arr[i++] = j;

				return new SlotRefArray(this, arr);
			}
		}

#if REVERSE_INDEX
		int _non_coref(int[] non_coref, List<int>[] L_coref)
		{
			int ncm_max = int.MinValue;

			for (int ix = 0; ix < count; ix++)
			{
				if (entries[ix].hash_code != -1)
				{
					int om = entries[ix].e_Mark;

					if (om > 0)
					{
						non_coref[om] = ix + 1;
						if (om > ncm_max)
							ncm_max = om;
					}
					else if (om < 0)
						(L_coref[~om] ?? (L_coref[~om] = new List<int>())).Add(ix + 1);
				}
			}
			return ncm_max;
		}

		SlotDictionary<int, HashSet<FeatMark>> reverse;

		public override Edge GetCorefEdge(int out_mark)
		{
			Debug.Assert(out_mark != 0);
			//if (out_mark == TopEdge.Mark && !(this is TfsBuilder.Xdl))
			//    return TopEdge;

			if (reverse == null)
				reverse = entries
							.Where(ate => ate.e_Mark != 0)
							.ToLookupDict(ate => ate.e_Mark, ate => ate.FeatMark);
			HashSet<FeatMark> hs;
			if (!reverse.TryGetValue(out_mark, out hs) || hs.Count == 0)
				return default(Edge);
			return hs.First().Constraint(this);
		}

		protected override ReadOnlyDictionary<int, int[]> _rebuild_reverse_index()
		{
			int[] non_coref = new int[next_mark];
			List<int>[] L_coref = new List<int>[c_corefs];
			int ncm_max = _non_coref(non_coref, L_coref);

			return non_coref
					.Take(ncm_max + 1)
					.TagIndex()
					.Where((a, om) => om == 1 || a.Item != 0)
					.Select(a => new KeyValuePair<int, int[]>(a.Index, new int[] { a.Item }))
					.Concat(L_coref.Select((L, notm) => new KeyValuePair<int, int[]>(~notm, alib.Enumerable._enumerable_ext._ToArray(L))))
					.ToReadOnlyDictionary();
		}

#else // REVERSE_INDEX
		public Edge GetCorefEdge(int m)
		{
			Debug.Assert(m != 0);
#if false
			for (int i = 0; i < c_act; i++)
				if (entries[i].hash_code != ListTerm && m == entries[i].e_Mark)
					return entries[i].e;
#else
			/// based on an empirical use pattern, we use the 'm' value here as an approximate
			/// starting point for a left/right alternating hunt. Note that this use (that is,
			/// as an index into the entries array) is never a correct interpretation of a 
			/// mark value. It's also a risky gamble for performance, since this jumping pattern
			/// (and with wrap-around) will not be friendly to the CPU cache. However, the way
			/// the TfsBuilder works, this typically results in e.g. 4-8 iterations versus 50 
			/// or more.
			if (m >= c_act)
				m = c_act - 1;
			for (int i = 1; i <= c_act; i++)
			{
				int v = i >> 1;
				if ((i & 1) != 0)
					v = -v;
				/// jump left or right, always centered around 'm'...
				v += m;
				/// ...but with wrap-around
				if (v >= c_act)
					v -= c_act;
				else if (v < 0)
					v += c_act;

				if (entries[v].hash_code != ListTerm && m == entries[v].e_Mark)
					return entries[v].e;
			}
#endif
			return default(Edge);
		}
#endif // REVERSE_INDEX

		public void CopyToArrayTfsEntries(arr_tfs_entry* pate)
		{
			fixed (arr_tfs_entry* p = entries)
				_copy_dict(pate, p, EdgeCount);
		}

		protected virtual void _copy_dict(arr_tfs_entry* dst, arr_tfs_entry* src, int c)
		{
			while (c > 0)
			{
				if (src->hash_code != ListTerm)
				{
					*dst = *src;
					dst++;
					c--;
				}
				src++;
			}
		}

		public sealed override bool TryGetEdge(int i_feat, int mark, out Edge e)
		{
			Debug.Assert(mark != 0);
			return TryGetValue(new FeatMark(i_feat, mark), out e);
		}

		public sealed override Edge.Flag TryGetFlagsMark(int i_feat, int mark, out int m)
		{
			Edge e;
			TryGetValue(new FeatMark(i_feat, mark), out e);
			m = e.Mark;
			return e.FlagsId;
		}


		public sealed override int GetEdgeIndex(int i_feat, int mark, Edge* pe)
		{
			int ix0 = FindEntry(new FeatMark(i_feat, mark));
			if (ix0 < 0)
				return 0;
			if (pe != null)
				*pe = entries[ix0].e;
			return ix0 + 1;
		}

		public void SetEdge(int i_feat, int mark, Edge e)
		{
			Debug.Assert(mark != 0);
			//tm.ValidateEdgeFlags(e);
			Debug.Assert(!e.Equals(default(Edge)));
			FeatMark fm = new FeatMark(i_feat, mark);
#if REVERSE_INDEX
			if (reverse != null)
			{
				Edge e_old;
				int m = e.Mark;
				if (TryGetValue(fm, out e_old))
				{
					if (e_old.Mark != m && e_old.Mark != 0)
						reverse[e_old.Mark].Remove(fm);
				}
				if (m != 0)
					reverse.AddToValueHashset(m, fm);
			}
#endif
			Insert(fm, e, false);
		}

		public bool RemoveEdge(int i_feat, int mark)
		{
			Debug.Assert(mark != 0);
			FeatMark fm = new FeatMark(i_feat, mark);
#if REVERSE_INDEX
			if (reverse != null)
			{
				Edge e;
				if (!TryGetValue(fm, out e))
					return false;
				HashSet<FeatMark> hs;
				int m = e.Mark;
				if (m != 0 && (hs = reverse[m]).Remove(fm) && hs.Count == 0)
					reverse.Remove(m);
			}
#endif
			return Remove(fm);
		}

		/// with transfer TFS now you have to be careful about which TypeManager applies
		public Edge CreateEdge(Type t, bool f_coref)
		{
			//Debug.Assert(t.tm == tm);
			Edge.Flag f = t.EdgeFlag;
			if (f_coref)
				return new Edge(f | Edge.Flag.Coreference, next_mark++);
			return new Edge(f, (f & Edge.Flag.EtmNonBareType) != 0 ? next_mark++ : 0);
		}

		public Edge CreateEdge(FeatMgr _fcm, Edge.Flag f, int m)
		{
			if ((f & Edge.Flag.NeedMark) != 0)
			{
				if (m == 0)
					m = next_mark++;
			}
			else if (m != 0)
				m = 0;
			return new Edge(f, m);
		}

		public Edge CreateEdge(Edge.Flag f, int m)
		{
			Debug.Assert(f != Edge.Flag.Bottom);
			if ((f & Edge.Flag.NeedMark) != 0)
			{
				if (m == 0)
					m = next_mark++;
			}
			else if (m != 0)
				m = 0;
			return new Edge(f, m);
		}

		int[] buckets;
		int count;
		int freeCount;
		int freeList;
		public const int ListTerm = -1;
		KeyCollection keys;
		ValueCollection values;

		void _initialize(int capacity)
		{
			int prime = alib.Math.Primes.HashFriendly(capacity);
			buckets = new int[prime];
			for (int i = 0; i < prime; i++)
				buckets[i] = ListTerm;
			entries = new arr_tfs_entry[prime];
			freeList = ListTerm;
		}

		public int FindEntry(FeatMark fm)
		{
			if (buckets != null)
			{
				int h = fm.GetHashCode();
				Debug.Assert(h != ListTerm);
				for (int i = buckets[h % buckets.Length]; i != ListTerm; i = entries[i]._next32)
					if (entries[i].hash_code == h)
						return i;
			}
			return -1;
		}

		public bool TryGetValue(FeatMark fm, out Edge e)
		{
			TypedReference tr;
			int h = fm.GetHashCode();
			Debug.Assert(h != ListTerm);
			int i = buckets[h % buckets.Length];
			while (i != ListTerm)
			{
				if ( __refvalue(tr = __makeref(entries[i]), arr_tfs_entry).hash_code == h)
				{
					e = __refvalue( tr, arr_tfs_entry).e;
					return true;
				}
				i = __refvalue( tr, arr_tfs_entry)._next32;
			}
			e = default(Edge);
			return false;
		}

		//public Edge this[FeatMark fm]
		//{
		//	get
		//	{
		//		int h = fm.GetHashCode();
		//		Debug.Assert(h != ListTerm);
		//		for (int i = buckets[h % buckets.Length]; i != ListTerm; i = entries[i]._next32)
		//			if (entries[i].hash_code == h)
		//				return entries[i].e;
		//		throw new KeyNotFoundException();
		//	}
		//	set { Insert(fm, value, false); }
		//}

		public void Add(FeatMark fm, Edge e)
		{
			Insert(fm, e, true);
		}

		public int GetOrCreateSlot(FeatMark fm)
		{
			if (buckets == null)
				_initialize(0);

			int h = fm.GetHashCode();
			Debug.Assert(h != ListTerm);
			int index = h % buckets.Length, i = buckets[index];
			TypedReference tr;
			while (i != ListTerm)
			{
				if ( __refvalue(tr = __makeref(entries[i]), arr_tfs_entry).hash_code == h)
					return i;
				i = __refvalue( tr, arr_tfs_entry)._next32;
			}
			if (freeCount > 0)
			{
				freeList = __refvalue( tr = __makeref(entries[i = freeList]), arr_tfs_entry)._next32;
				freeCount--;
				c_act++;
			}
			else
			{
				if (count == entries.Length)
				{
					Resize();
					index = h % buckets.Length;
				}
				tr = __makeref(entries[i = this.count]);
				this.count++;
				this.c_act++;
			}
			__refvalue( tr, arr_tfs_entry).hash_code = h;
			__refvalue( tr, arr_tfs_entry)._next32 = buckets[index];
			buckets[index] = i;
			return i;
		}

		void Insert(FeatMark fm, Edge e, bool f_add)
		{
			if (buckets == null)
				_initialize(0);

			int h = fm.GetHashCode();
			Debug.Assert(h != ListTerm);
			int index = h % buckets.Length, i = buckets[index];
			TypedReference tr;
			while (i != ListTerm)
			{
				if ( __refvalue(tr = __makeref(entries[i]), arr_tfs_entry).hash_code == h)
				{
					if (f_add)
						throw new ArgumentException();
					__refvalue(tr, arr_tfs_entry).e = e;
					return;
				}
				i = __refvalue( tr, arr_tfs_entry)._next32;
			}
			if (freeCount > 0)
			{
				freeList = __refvalue( tr = __makeref(entries[i = freeList]), arr_tfs_entry)._next32;
				freeCount--;
				c_act++;
			}
			else
			{
				if (count == entries.Length)
				{
					Resize();
					index = h % buckets.Length;
				}
				tr = __makeref(entries[i = this.count]);
				this.count++;
				this.c_act++;
			}
			__refvalue( tr, arr_tfs_entry).hash_code = h;
			__refvalue( tr, arr_tfs_entry)._next32 = buckets[index];
			__refvalue( tr, arr_tfs_entry).e = e;
			buckets[index] = i;
		}

		public bool Remove(FeatMark fm)
		{
			if (buckets != null)
			{
				int h = fm.GetHashCode();
				Debug.Assert(h != ListTerm);
				int index = h % buckets.Length, i = buckets[index], j = ListTerm;
				TypedReference tr;
				while (i != ListTerm)
				{
					if ( __refvalue(tr = __makeref(entries[i]), arr_tfs_entry).hash_code == h)
					{
						if (j != ListTerm)
							entries[j]._next32 = __refvalue( tr, arr_tfs_entry)._next32;
						else
							buckets[index] = __refvalue( tr, arr_tfs_entry)._next32;
						__refvalue(tr, arr_tfs_entry).hash_code = ListTerm;
						__refvalue(tr, arr_tfs_entry)._next32 = freeList;
						__refvalue(tr, arr_tfs_entry).e = default(Edge);
						freeList = i;
						freeCount++;
						c_act--;
						return true;
					}
					j = i;
					i = __refvalue( tr, arr_tfs_entry)._next32;
				}
			}
			return false;
		}

		void Resize()
		{
			int prime = alib.Math.Primes.HashFriendly(count * 2);
			int[] numArray = new int[prime];
			fixed (int* _ph = numArray)
			{
				int* ph = _ph;
				for (int i = 0; i < prime; i++, ph++)
					*ph = ListTerm;

				arr_tfs_entry[] new_arr = new arr_tfs_entry[prime];
				fixed (arr_tfs_entry* _dst = new_arr)
				{
					fixed (arr_tfs_entry* _src = entries)
						alib.Memory.Kernel32.CopyMemory(_dst, _src, count * sizeof(arr_tfs_entry));

					arr_tfs_entry* dst = _dst;
					for (int j = 0; j < count; j++, dst++)
					{
						int index = dst->hash_code % prime;
						dst->_next32 = _ph[index];
						_ph[index] = j;
					}
				}
				this.buckets = numArray;
				this.entries = new_arr;
			}
		}

		public void Clear()
		{
			if (count > 0)
			{
				for (int i = 0; i < buckets.Length; i++)
					buckets[i] = ListTerm;
				System.Array.Clear(entries, 0, count);
				freeList = ListTerm;
				c_act = 0;
				count = 0;
				freeCount = 0;
			}
		}

		public bool ContainsKey(FeatMark fm)
		{
			return FindEntry(fm) != -1;
		}

		public bool ContainsValue(Edge e)
		{
			for (int j = 0; j < count; j++)
				if (entries[j].hash_code != ListTerm && entries[j].e.Equals(e))
					return true;
			return false;
		}

		void CopyTo(FeatMarkEdge[] array, int index)
		{
			if (array == null)
				throw new ArgumentNullException();
			if (index < 0 || index > array.Length)
				throw new ArgumentOutOfRangeException();
			if ((array.Length - index) < this.EdgeCount)
				throw new ArgumentException();

			int c = this.count;
			arr_tfs_entry[] _tmp = this.entries;
			for (int i = 0; i < c; i++)
				if (_tmp[i].hash_code != ListTerm)
					array[index++] = new FeatMarkEdge(_tmp[i].FeatMark, _tmp[i].e);
		}
#if false
		void ICollection<FeatMarkEdge>.Add(FeatMarkEdge kvp)
		{
			Add(kvp.Key, kvp.Value);
		}

		bool ICollection<FeatMarkEdge>.Contains(FeatMarkEdge kvp)
		{
			int index = FindEntry(kvp.Key);
			return index != -1 && entries[index].e.Equals(kvp.Value);
		}

		void ICollection<FeatMarkEdge>.CopyTo(FeatMarkEdge[] array, int index)
		{
			this.CopyTo(array, index);
		}

		bool ICollection<FeatMarkEdge>.Remove(FeatMarkEdge kvp)
		{
			int index = FindEntry(kvp.Key);
			if (index != -1 && entries[index].e.Equals(kvp.Value))
			{
				Remove(kvp.Key);
				return true;
			}
			return false;
		}
		IEnumerator<FeatMarkEdge> IEnumerable<FeatMarkEdge>.GetEnumerator() { return new Enumerator(this, 2); }
		IEnumerator IEnumerable.GetEnumerator() { return new Enumerator(this, 2); }
		public Enumerator GetEnumerator() { return new Enumerator(this, 2); }
#endif
		public IEnumerable<FeatMarkEdge> _fme_enum()
		{
			var e = new Enumerator(this, 2);
			while (e.MoveNext())
				yield return e.Current;
		}

		public IEqualityComparer<FeatMark> Comparer { get { return EqualityComparer<FeatMark>.Default; } }
#if false
		void ICollection.CopyTo(System.Array array, int index)
		{
			if (array == null)
				throw new ArgumentNullException();
			if (array.Rank != 1)
				throw new ArgumentException();
			if (array.GetLowerBound(0) != 0)
				throw new ArgumentException();
			if (index < 0 || index > array.Length)
				throw new ArgumentOutOfRangeException();
			if ((array.Length - index) < this.Count)
				throw new ArgumentException();

			FeatMarkEdge[] pairArray = array as FeatMarkEdge[];
			arr_tfs_entry[] _tmp;

			if (pairArray != null)
				CopyTo(pairArray, index);
			else if (array is DictionaryEntry[])
			{
				DictionaryEntry[] entryArray = array as DictionaryEntry[];
				_tmp = this.entries;
				for (int i = 0; i < count; i++)
					if (_tmp[i].hash_code != ListTerm)
						entryArray[index++] = new DictionaryEntry(_tmp[i].FeatMark, _tmp[i].e);
			}
			else
			{
				object[] objArray = array as object[];
				if (objArray == null)
					throw new ArgumentException();

				_tmp = this.entries;
				for (int j = 0; j < count; j++)
					if (_tmp[j].hash_code != ListTerm)
						objArray[index++] = new FeatMarkEdge(_tmp[j].FeatMark, _tmp[j].e);
			}
		}
		bool ICollection.IsSynchronized { get { return false; } }
		object ICollection.SyncRoot { get { return this; } }
		ICollection<FeatMark> IDictionary<FeatMark, Edge>.Keys { get { return keys ?? (keys = new KeyCollection(this)); } }
		ICollection<Edge> IDictionary<FeatMark, Edge>.Values { get { return values ?? (values = new ValueCollection(this)); } }
		bool ICollection<FeatMarkEdge>.IsReadOnly { get { return false; } }
#endif
		public KeyCollection Keys { get { return keys ?? (keys = new KeyCollection(this)); } }
		public ValueCollection Values { get { return values ?? (values = new ValueCollection(this)); } }

		public struct Enumerator : IEnumerator<FeatMarkEdge>, IDisposable, IDictionaryEnumerator, IEnumerator
		{
			const int DictEntry = 1;
			const int KeyValuePair = 2;

			WriteableTfs dict;
			FeatMarkEdge cur;
			int ix;
			int m_type;
			public Enumerator(WriteableTfs dictionary, int _type)
			{
				this.dict = dictionary;
				this.ix = 0;
				this.m_type = _type;
				cur = default(FeatMarkEdge);
			}

			public bool MoveNext()
			{
				while (ix < dict.count)
				{
					if (dict.entries[ix].hash_code != ListTerm)
					{
						cur = new FeatMarkEdge(dict.entries[ix].FeatMark, dict.entries[ix].e);
						ix++;
						return true;
					}
					ix++;
				}
				ix = dict.count + 1;
				cur = default(FeatMarkEdge);
				return false;
			}

			public FeatMarkEdge Current { get { return cur; } }
			public void Dispose() { }

			object IEnumerator.Current
			{
				get
				{
					if (ix == 0 || ix == (dict.count + 1))
						throw new InvalidOperationException();
					if (m_type == 1)
						return new DictionaryEntry(cur.Key, cur.Value);
					return new FeatMarkEdge(cur.Key, cur.Value);
				}
			}
			void IEnumerator.Reset()
			{
				ix = 0;
				cur = new FeatMarkEdge();
			}

			DictionaryEntry IDictionaryEnumerator.Entry
			{
				get
				{
					if (ix == 0 || ix == (dict.count + 1))
						throw new InvalidOperationException();
					return new DictionaryEntry(cur.Key, cur.Value);
				}
			}
			object IDictionaryEnumerator.Key
			{
				get
				{
					if (ix == 0 || ix == (dict.count + 1))
						throw new InvalidOperationException();
					return cur.Key;
				}
			}
			object IDictionaryEnumerator.Value
			{
				get
				{
					if (ix == 0 || ix == (dict.count + 1))
						throw new InvalidOperationException();
					return cur.Value;
				}
			}
		};

		[DebuggerDisplay("Count = {Count}")]
		public sealed class KeyCollection : _ICollection<FeatMark>, ISet<FeatMark>
		{
			readonly WriteableTfs dict;

			public KeyCollection(WriteableTfs dictionary)
			{
				if (dictionary == null)
					throw new ArgumentNullException();
				this.dict = dictionary;
			}

			public void CopyTo(FeatMark[] array, int index)
			{
				if (array == null)
					throw new ArgumentNullException();
				if (index < 0 || index > array.Length)
					throw new ArgumentOutOfRangeException();
				if ((array.Length - index) < dict.EdgeCount)
					throw new ArgumentException();

				int c = dict.count;
				arr_tfs_entry[] _tmp = dict.entries;
				for (int i = 0; i < c; i++)
					if (_tmp[i].hash_code != ListTerm)
						array[index++] = _tmp[i].FeatMark;
			}

			bool ICollection<FeatMark>.Contains(FeatMark item) { return dict.ContainsKey(item); }
			public Enumerator GetEnumerator() { return new Enumerator(dict); }
			IEnumerator<FeatMark> IEnumerable<FeatMark>.GetEnumerator() { return new Enumerator(dict); }
			void ICollection<FeatMark>.Add(FeatMark item) { throw new NotSupportedException(); }
			void ICollection<FeatMark>.Clear() { throw new NotSupportedException(); }
			bool ICollection<FeatMark>.Remove(FeatMark item) { throw new NotSupportedException(); }
			IEnumerator IEnumerable.GetEnumerator() { return new Enumerator(dict); }
			public int Count { get { return dict.EdgeCount; } }
			bool ICollection<FeatMark>.IsReadOnly { get { return true; } }
			bool ICollection.IsSynchronized { get { return false; } }
			object ICollection.SyncRoot { get { return dict; } }

			void ICollection.CopyTo(System.Array array, int index)
			{
				if (array == null)
					throw new ArgumentNullException();
				if (array.Rank != 1)
					throw new ArgumentException();
				if (array.GetLowerBound(0) != 0)
					throw new ArgumentException();
				if (index < 0 || index > array.Length)
					throw new ArgumentOutOfRangeException();
				if ((array.Length - index) < this.Count)
					throw new ArgumentException();

				int c = dict.count;
				FeatMark[] localArray = array as FeatMark[];
				if (localArray != null)
				{
					CopyTo(localArray, index);
				}
				else
				{
					object[] objArray = array as object[];
					if (objArray == null)
						throw new ArgumentException();

					arr_tfs_entry[] _tmp = dict.entries;
					for (int i = 0; i < c; i++)
						if (_tmp[i].hash_code != ListTerm)
							objArray[index++] = _tmp[i].FeatMark;
				}
			}

			public struct Enumerator : IEnumerator<FeatMark>, IDisposable, IEnumerator
			{
				WriteableTfs dict;
				int ix;
				FeatMark cur;
				public Enumerator(WriteableTfs dictionary)
				{
					this.dict = dictionary;
					this.ix = 0;
					this.cur = default(FeatMark);
				}

				public void Dispose() { }

				public bool MoveNext()
				{
					while (ix < dict.count)
					{
						if (dict.entries[ix].hash_code != ListTerm)
						{
							cur = dict.entries[ix].FeatMark;
							ix++;
							return true;
						}
						ix++;
					}
					ix = dict.count + 1;
					cur = default(FeatMark);
					return false;
				}

				public FeatMark Current { get { return cur; } }
				object IEnumerator.Current
				{
					get
					{
						if (ix == 0 || (ix == (dict.count + 1)))
							throw new InvalidOperationException();
						return cur;
					}
				}
				void IEnumerator.Reset()
				{
					ix = 0;
					cur = default(FeatMark);
				}
			}

			/// <summary>
			/// ISet(FeatMark)
			/// </summary>

			public bool IsProperSubsetOf(IEnumerable<FeatMark> other)
			{
				throw not.impl;
			}

			public bool IsProperSupersetOf(IEnumerable<FeatMark> other)
			{
				throw not.impl;
			}

			public bool IsSubsetOf(IEnumerable<FeatMark> other)
			{
				throw not.impl;
			}

			public bool IsSupersetOf(IEnumerable<FeatMark> other)
			{
				throw not.impl;
			}

			public bool Overlaps(IEnumerable<FeatMark> other)
			{
				throw not.impl;
			}

			public bool SetEquals<TExt>(Dictionary<FeatMark, TExt>.KeyCollection other)
			{
				if (other.Count != dict.EdgeCount)
					return false;
				var ie = other.GetEnumerator();
				while (ie.MoveNext())
					if (dict.FindEntry(ie.Current) == -1)
						return false;
				return true;
			}
			public bool SetEquals(IEnumerable<FeatMark> other)
			{
				if (other == null)
					return false;
				if (Object.ReferenceEquals(this, other))
					return true;

				ISet<FeatMark> is1;

				int c_coll, c_set = dict.EdgeCount;
				if ((is1 = other as ISet<FeatMark>) != null)
				{
					if (c_set != is1.Count)
						return false;

					IEqualityComparer<FeatMark> _cmp = null;
					KeyCollection _kc;
					HashSet<FeatMark> _hs;
					if ((_kc = is1 as KeyCollection) != null)
						_cmp = _kc.dict.Comparer;
					else if ((_hs = is1 as HashSet<FeatMark>) != null)
						_cmp = _hs.Comparer;

					if (_cmp != null && Object.ReferenceEquals(dict.Comparer, _cmp))
					{
						var ie = is1.GetEnumerator();
						while (ie.MoveNext())
							if (dict.FindEntry(ie.Current) == -1)
								return false;
						return true;
					}
					goto full;
				}
				else if ((c_coll = other.CountIfAvail<FeatMark>()) != -1)
				{
				}
				else if (c_set == 0)
					return !other.GetEnumerator().MoveNext();
				else
					goto full;

				if (c_coll < c_set || (c_set == 0 && c_coll > 0))
					return false;
			full:
				return CountUnique(other) == c_set;
			}

			int CountUnique(IEnumerable<FeatMark> other)
			{
				int ix, c_marked = 0;
				int n = ((dict.count - 1) >> 6) + 1;
				ulong* bitArrayPtr = stackalloc ulong[n];
				alib.Bits.BitHelper helper = new alib.Bits.BitHelper(bitArrayPtr, n);

				var ie = other.GetEnumerator();
				while (ie.MoveNext())
					if ((ix = dict.FindEntry(ie.Current)) == -1)
						return -1;
					else if (!helper.IsMarked(ix))
					{
						helper.SetBit(ix);
						c_marked++;
					}
				return c_marked;
			}

			bool ISet<FeatMark>.Add(FeatMark item) { throw new InvalidOperationException(); }
			public void SymmetricExceptWith(IEnumerable<FeatMark> other) { throw new InvalidOperationException(); }
			public void UnionWith(IEnumerable<FeatMark> other) { throw new InvalidOperationException(); }
			public void ExceptWith(IEnumerable<FeatMark> other) { throw new InvalidOperationException(); }
			public void IntersectWith(IEnumerable<FeatMark> other) { throw new InvalidOperationException(); }
		};

		[DebuggerDisplay("Count = {Count}")]
		public sealed class ValueCollection : _ICollection<Edge>
		{
			WriteableTfs dict;

			public ValueCollection(WriteableTfs dictionary)
			{
				if (dictionary == null)
					throw new ArgumentNullException();
				this.dict = dictionary;
			}

			public void CopyTo(Edge[] array, int index)
			{
				if (array == null)
					throw new ArgumentNullException();
				if (index < 0 || index > array.Length)
					throw new ArgumentOutOfRangeException();
				if ((array.Length - index) < dict.EdgeCount)
					throw new ArgumentException();

				int c = dict.count;
				arr_tfs_entry[] _tmp = dict.entries;
				for (int i = 0; i < c; i++)
					if (_tmp[i].hash_code != ListTerm)
						array[index++] = _tmp[i].e;
			}

			public IEnumerator<Edge> GetEnumerator() { return new Enumerator(dict); }
			void ICollection<Edge>.Add(Edge item) { throw new NotSupportedException(); }
			void ICollection<Edge>.Clear() { throw new NotSupportedException(); }
			bool ICollection<Edge>.Contains(Edge item) { return dict.ContainsValue(item); }
			bool ICollection<Edge>.Remove(Edge item) { throw new NotSupportedException(); }
			IEnumerator IEnumerable.GetEnumerator() { return new Enumerator(dict); }
			public int Count { get { return dict.EdgeCount; } }
			bool ICollection<Edge>.IsReadOnly { get { return true; } }
			bool ICollection.IsSynchronized { get { return false; } }
			object ICollection.SyncRoot { get { return dict; } }

			void ICollection.CopyTo(System.Array array, int index)
			{
				if (array == null)
					throw new ArgumentNullException();
				if (array.Rank != 1)
					throw new ArgumentException();
				if (array.GetLowerBound(0) != 0)
					throw new ArgumentException();
				if (index < 0 || index > array.Length)
					throw new ArgumentOutOfRangeException();
				if ((array.Length - index) < this.Count)
					throw new ArgumentException();

				Edge[] localArray = array as Edge[];
				if (localArray != null)
				{
					CopyTo(localArray, index);
				}
				else
				{
					object[] objArray = array as object[];
					if (objArray == null)
						throw new ArgumentException();

					int c = dict.count;
					arr_tfs_entry[] _tmp = dict.entries;
					for (int i = 0; i < c; i++)
						if (_tmp[i].hash_code != ListTerm)
							objArray[index++] = _tmp[i].e;
				}
			}

			public struct Enumerator : IEnumerator<Edge>, IDisposable, IEnumerator
			{
				WriteableTfs dict;
				int ix;
				Edge cur;
				public Enumerator(WriteableTfs dictionary)
				{
					this.dict = dictionary;
					this.ix = 0;
					this.cur = default(Edge);
				}

				public void Dispose() { }

				public bool MoveNext()
				{
					while (ix < dict.count)
					{
						if (dict.entries[ix].hash_code != ListTerm)
						{
							cur = dict.entries[ix].e;
							ix++;
							return true;
						}
						ix++;
					}
					ix = dict.count + 1;
					cur = default(Edge);
					return false;
				}

				public Edge Current { get { return cur; } }
				object IEnumerator.Current
				{
					get
					{
						if (ix == 0 || (ix == dict.count + 1))
							throw new InvalidOperationException();
						return cur;
					}
				}
				void IEnumerator.Reset()
				{
					ix = 0;
					cur = default(Edge);
				}
			}
		};
#if DICT
		};
#endif
	};
}
